//
//
#ifndef Graph_h__
#define Graph_h__

#include "Matrix.h"

namespace Structure
{
	template<class Number>
	class GraphStructure
	{
	public:
		// constructor
		GraphStructure(){}
		// destructor
		virtual ~GraphStructure(){}

		/* static basic function about value(class Number) */
	public:
		// get static object(zero:0)
		static inline const Number& getNumberZero()
		{
			static const Number number(0);
			return number;
		}

		// get static object(zero:-1)
		static inline const Number& getNumberEndless()
		{
			static const Number number(-1);
			return number;
		}

		// get static invalid node position
		static inline const unsigned int getNPos()
		{
			static const unsigned int npos = -1;
			return npos;
		}

		/* basic function */
	public:
		// if it is valid
		inline virtual bool isValid() = 0;
		// allocate buffer
		inline virtual void alloc(unsigned int _length) = 0;
		// free all the buffer
		inline virtual void free() = 0;
		// copy the data
		inline virtual void copy(GraphStructure* _graphst) = 0;

	public:
		// count total nodes
		inline virtual unsigned int countNodes() = 0;
		// count total edges
		inline virtual unsigned int countEdges() = 0;
		// get the first adjacency node index 
		inline virtual unsigned int getFirstNode(unsigned int _cur) = 0;
		// get the next adjacency node index 
		inline virtual unsigned int getNextNode(unsigned int _cur, unsigned int _adj_node) = 0;
		// get the edge value
		inline virtual const Number& getEdgeValue(unsigned int _start, unsigned int _end) = 0;
		// set the edge value
		inline virtual bool setEdgeValue(unsigned int _start, unsigned int _end, const Number& _value) = 0;
	};


	template<class Number>
	class AdjMatrix : public GraphStructure<Number>
	{
	public:
		// type define AdjMatrix, Number
		typedef typename GraphStructure<Number> _GraphStructure;
		typedef typename AdjMatrix<Number> _AdjMatrix;
		typedef typename Geometric::Matrix<Number> _Matrix;
		typedef typename Number _Number;

	public:
		AdjMatrix() :m_edge_matrix()
		{
		}
		
		explicit AdjMatrix(const AdjMatrix& _adjmat) 
			:m_edge_matrix(_adjmat.m_edge_matrix)
		{
		}
		
		virtual ~AdjMatrix()
		{
			free();
		}

	protected:
		// store the adjacency matrix edge value
		_Matrix m_edge_matrix;

	public:
		inline virtual bool isValid()
		{
			// node data is unnecessary, so effectiveness depend on adjacency matrix
			return m_edge_matrix.isOrderMatrix();
		}

		inline virtual void alloc(unsigned int _length)
		{
			// allocate memory to adjacency matrix to store edge data
			m_edge_matrix.alloc(_length, _length);
			// initialize data
			initialize();
		}

		inline virtual void free()
		{
			// free all buffer of matrix
			m_edge_matrix.free();
		}

		inline virtual void copy(_GraphStructure* _adjst)
		{
			_AdjMatrix* adjmat = dynamic_cast<_AdjMatrix*>(_adjst);
			copy(*adjmat);
		}

	public:
		inline virtual unsigned int countNodes()
		{
			return m_edge_matrix.getI();
		}

		inline virtual unsigned int countEdges()
		{
			unsigned int count = 0;
			unsigned int node_count = m_edge_matrix.getI();
			const Number& zero = _GraphStructure::getNumberZero();
			const Number& endless = _GraphStructure::getNumberEndless();

			for(unsigned int i = 0; i < node_count; i++)
			{
				for(unsigned int j = 0; j < node_count; j++)
				{
					Number& value = m_edge_matrix.at(i, j);
					if(i != j && value != zero && value != endless)
					{
						// if edge value is valid
						count++;
					}
				}
			}
			// return result
			return count;
		}

	public:
		inline virtual unsigned int getFirstNode(unsigned int _cur)
		{
			Number zero(0);
			for(unsigned int j = 0; j < m_edge_matrix.getJ(); j++)
			{
				if(j != _cur && m_edge_matrix.at(_cur, j) != _GraphStructure::getNumberEndless())
				{
					return j;
				}
			}
			// do not find
			return _GraphStructure::getNPos();
		}

		inline virtual unsigned int getNextNode(unsigned int _cur, unsigned int _adj_node)
		{
			for(unsigned int j = _adj_node+1; j < m_edge_matrix.getJ(); j++)
			{
				if(j != _cur && m_edge_matrix.at(_cur, j) != _GraphStructure::getNumberEndless())
				{
					return j;
				}
			}
			// do not find
			return _GraphStructure::getNPos();
		}

		inline virtual const Number& getEdgeValue(unsigned int _start, unsigned int _end)
		{
			unsigned int node_count = countNodes();
			if(_start < node_count && _end < node_count)
			{
				return m_edge_matrix.at(_start, _end);
			}
			// invalid node index
			return _GraphStructure::getNumberEndless();
		}

		inline virtual bool setEdgeValue(unsigned int _start, unsigned int _end, const Number& _value)
		{
			unsigned int node_count = countNodes();
			if(_start < node_count && _end < node_count
				&& _value != _GraphStructure::getNumberZero())
			{
				m_edge_matrix.set(_start, _end, _value);
				return true;
			}
			// invalid node index
			return false;
		}

	protected:
		inline void initialize()
		{
			const Number& zero = _GraphStructure::getNumberZero();
			const Number& endless = _GraphStructure::getNumberEndless();
			unsigned int node_count = m_edge_matrix.getI();
			for(unsigned int i = 0; i < node_count; i++)
			{
				for(unsigned int j = 0; j < node_count; j++)
				{
					// set value
					if(i == j)
					{
						m_edge_matrix.set(i, j, zero);
					}
					else
					{
						m_edge_matrix.set(i, j, endless);
					}
				}
			}
		}

		inline void copy(const _AdjMatrix& _adjmat)
		{
			m_edge_matrix = _adjmat.m_edge_matrix;
		}
	};

	template<class Number>
	class AdjList : public GraphStructure<Number>
	{
	public:
		// type define AdjList, Number
		typedef typename GraphStructure<Number> _GraphStructure;
		typedef typename AdjList<Number> _AdjList;
		typedef typename Number _Number;
	public:
		// type define adjacency edge
		typedef struct AdjListEdge
		{
			// point to end node number
			unsigned int m_end_node;
			// graph edge data value
			Number m_value;
			// point to the next edge
			AdjListEdge* m_next;
		}_AdjListEdge;
		// type define adjacency node
		typedef struct AdjListNode
		{
			// count of edges of a node
			unsigned int m_edge_count;
			// point to edge array head address
			AdjListEdge* m_edge_array;
		}_AdjListNode;

	public:
		AdjList() :m_node_count(0), m_node_array(NULL)
		{
		}

		explicit AdjList(const AdjList& _adjlist)
		{
			copy(_adjlist);
		}

		~AdjList()
		{
			free();
		}

	protected:
		// number of nodes in array
		unsigned int m_node_count;
		// point to node array head address
		AdjListNode* m_node_array;

	public:
		inline virtual bool isValid()
		{
			return (m_node_count != 0 && m_node_array != NULL);
		}

		inline virtual void alloc(unsigned int _length)
		{
			// free all the data buffer
			free();

			// allocate and initialize node array
			m_node_count = _length;
			m_node_array = new AdjListNode[m_node_count];

			// allocate head node
			initialize();
		}

		inline virtual void free()
		{
			// delete all edges data
			freeEdgesList();

			// delete all nodes data
			delete[] m_node_array;
			m_node_array = NULL;
		}

		inline virtual void copy(_GraphStructure* _adjst)
		{
			_AdjList* adjlist = dynamic_cast<_AdjList*>(_adjst);
			copy(*adjlist);
		}

	public:
		inline virtual unsigned int countNodes()
		{
			return m_node_count;
		}

		inline virtual unsigned int countEdges()
		{
			unsigned int count = 0;
			for(unsigned int i = 0; i < m_node_count; i++)
			{
				count += m_node_array[i].m_edge_count;
			}
			// return result
			return count;
		}

		inline virtual unsigned int getFirstNode(unsigned int _cur)
		{
			_AdjListEdge* head = m_node_array[_cur].m_edge_array;
			if(head->m_next != NULL)
			{
				return head->m_next->m_end_node;	 
			}
			else
			{
				return _GraphStructure::getNPos();
			}
		}
		
		inline virtual unsigned int getNextNode(unsigned int _cur, unsigned int _adj_node)
		{
			_AdjListEdge* cur = m_node_array[_cur].m_edge_array;
			while(cur != NULL && cur->m_end_node != _adj_node)
			{
				cur = cur->m_next;
			}

			if(cur != NULL)
			{
				if(cur->m_next != NULL)
				{
					return cur->m_next->m_end_node;
				}
			}
			// not find
			return _GraphStructure::getNPos();
		}

		inline virtual const Number& getEdgeValue(unsigned int _start, unsigned int _end)
		{
			AdjListEdge* head = m_node_array[_start].m_edge_array;
			AdjListEdge* edge = head->m_next;
			while(edge != NULL)
			{
				// find specify edge, then return
				if(edge->m_end_node == _end)
				{
					return edge->m_value;
				}
				// to next
				edge = edge->m_next;
			}

			// not find, return endless as result
			return _GraphStructure::getNumberEndless();
		}

		inline virtual bool setEdgeValue(unsigned int _start, unsigned int _end, const Number& _value)
		{
			if(_start < m_node_count && _end < m_node_count 
				&& _start != _end && _value != _GraphStructure::getNumberZero())
			{
				AdjListEdge* pre = m_node_array[_start].m_edge_array;
				AdjListEdge* cur = pre->m_next;
				while(cur != NULL)
				{
					// find specify edge, then break
					if(cur->m_end_node == _end)
					{
						break;
					}
					// to next
					pre = cur;
					cur = cur->m_next;
				}

				// insert/reset or delete
				if(_value == _GraphStructure::getNumberEndless())
				{
					if(cur != NULL)
					{
						// delete an edge
						pre->m_next = cur->m_next;
						delete cur;
						m_node_array[_start].m_edge_count--;
					}
				}
				else
				{
					if(cur == NULL)
					{
						// insert an edge
						AdjListEdge* edge = new AdjListEdge();
						edge->m_end_node = _start;
						edge->m_value = _value;
						edge->m_next = cur;
						pre->m_next = edge;
						m_node_array[_start].m_edge_count++;
					}
					else
					{
						// reset edge value
						cur->m_value = _value;
					}
				}
				// finish
				return true;
			}
			// invalid node index
			return false;
		}

	protected:
		inline void initialize()
		{
			for(unsigned int i = 0; i < m_node_count; i++)
			{
				AdjListEdge* head = new AdjListEdge();
				head->m_end_node = _GraphStructure::getNPos();
				head->m_value = _GraphStructure::getNumberEndless();
				head->m_next = NULL;
				m_node_array[i].m_edge_array = head;
				m_node_array[i].m_edge_count = 0;
			}
		}

		inline void freeEdgesList()
		{
			// delete all edges data
			for(unsigned int i = 0; i < m_node_count; i++)
			{
				AdjListEdge* cur = m_node_array[i].m_edge_array;
				while(cur != NULL)
				{
					AdjListEdge* next = cur->m_next;
					delete cur;
					cur = next;
				}
				// reset
				m_node_array[i].m_edge_array = NULL;
				m_node_array[i].m_edge_count = 0;
			}
		}

		inline void copy(const AdjList& _adjlist)
		{
			// allocate buffer for node array
			alloc(_adjlist.m_node_count);

			// copy the edge data
			for(unsigned int i = 0; i < m_node_count; i++)
			{
				m_node_array[i].m_edge_count = _adjlist.m_node_array[i].m_edge_count;
				AdjListEdge* edge = _adjlist.m_node_array[i].m_edge_array;
				
				AdjListEdge* pre = edge;
				AdjListEdge* cur = NULL;
				while(edge != NULL)
				{
					cur = new AdjListEdge();
					cur->m_end_node = edge->m_end_node;
					cur->m_value = edge->m_value;
					cur->m_next = NULL;
					
					// assign value
					pre->m_next = cur;
					
					// get next edge data
					edge = edge->m_next;
				}// while
			}// for
		}
	};



	template<class Number>
	class _GEOMETRIC Graph
	{
	public:
		// type define Graph and Number
		typedef typename GraphStructure<Number> _GraphStructure;
		typedef typename Graph<Number> _Graph;
		typedef typename AdjMatrix<Number> _AdjMatrix;
		typedef typename AdjList<Number> _AdjList;
		typedef typename Number _Number;
		typedef void (*Function)(unsigned int);
	public:
		// type define AdjStType, it is the flag of storage type
		typedef enum AdjStType
		{
			EAT_Unvalid = 0x0,
			EAT_AdjMatrix,
			EAT_AdjList
		}_AdjStType;

	public:
		Graph() :m_type(EAT_Unvalid), m_data(NULL)
		{
		}

		Graph(const Graph& _graph) :m_type(EAT_Unvalid), m_data(NULL)
		{
			copy(_graph);
		}

		virtual ~Graph()
		{
			free();
		}

	public:
		// point to data of graph
		_GraphStructure* m_data;
		// the storage type of graph data
		AdjStType m_type;

	public:
		inline virtual bool isValid()
		{
			return (m_type != EAT_Unvalid && m_data->isValid() != false);
		}

		inline virtual void alloc(AdjStType _type)
		{
			// free old data
			free();
			
			// allocate new type data
			m_type = _type;
			if(m_type == EAT_AdjMatrix)
			{
				m_data = new AdjMatrix<Number>();
			}
			else if(m_type == EAT_AdjList)
			{
				m_data = new AdjList<Number>();
			}
		}

		inline virtual void free()
		{
			m_type = EAT_Unvalid;
			delete m_data;
			m_data = NULL;
		}

		inline virtual void copy(const Graph& _graph)
		{
			alloc(_graph.m_type);
			m_data->copy(_graph.m_data);
		}

	public:
		inline virtual unsigned int countNodes()
		{
			return m_data->countNodes();
		}

		inline virtual unsigned int countEdges()
		{
			return m_data->countEdges();
		}

		inline virtual unsigned int getFirstNode(unsigned int _cur)
		{
			return m_data->getFirstNode(_cur);
		}

		inline virtual unsigned int getNextNode(unsigned int _cur, unsigned int _adj_node)
		{
			return m_data->getNextNode(_cur, _adj_node);
		}

		inline bool setEdgeValue(unsigned int _start, unsigned int _end, const Number& _value)
		{
			return m_data->setEdgeValue(_start, _end, _value);
		}

		inline const Number& getEdgeValue(unsigned int _start, unsigned int _end)
		{
			return m_data->getEdgeValue(_start, _end);
		}

		inline bool isValidEdgeValue(const Number& _number)
		{
			return (_GraphStructure::getNumberEndless() != _number);
		}

		inline bool isValidNode(unsigned int _index)
		{
			return (_index < m_data->countNodes());
		}

	public:
		// breadth-first traversal
		inline void traverseBFS(unsigned int _begin, Function _func)
		{
			if(isValid() == false || isValidNode(_begin) == false)
			{
				// it is not valid
				return;
			}

			// BFS process
			unsigned int node_count = countNodes();
			unsigned int* que = new unsigned int[node_count](_GraphStructure::getNPos());	
			unsigned int head = 0, tail = 0;
			unsigned int cur = _begin, next = _begin;

			// if the begin node is belong to the graph
			que[tail++] = cur;

			// if the queue is not empty
			while(head < tail)
			{
				// dequeue
				cur = que[head++];

				// function call
				_func(cur);

				// get the node first adjacency node
				next = m_data->getFirstNode(cur);

				// enqueue all adjacency nodes
				while(isValidNode(next) == true)
				{
					// enqueue
					que[tail++] = next;
					// get the next adjacency node
					next = m_data->getNextNode(cur, next);
				}
			}

			// free the buffer
			delete[] que;
		}

		// depth-first traversal
		inline void traverseDFS(unsigned int _begin, Function _func)
		{
			if(isValid() == true || isValidNode(_begin) == false)
			{
				// it is not valid
				return;
			}

			// DFS process
			unsigned int node_count = m_data->countNodes();
			unsigned int* stack = new unsigned int[node_count](_GraphStructure::getNPos());
			unsigned int top = 0;
			unsigned int cur = _begin, next = _begin;

			// if the begin node is belong to the graph
			stack[top++] = cur;

			// if the stack is not empty
			while(top > 0)
			{
				// pop
				cur = stack[--top];

				// function call
				_func(cur);

				// get the node first adjacency node
				next = m_data->getFirstNode(cur);

				// push all adjacency nodes into stack
				while(isValidNode(next) == true)
				{
					// push
					stack[top++] = next;
					// get the next adjacency node
					next = m_data->getNextNode(cur, next);
				}
			}

			// free the buffer
			delete[] stack;
		}

	public:
		inline bool doDijkstra(unsigned int _start, Geometric::Matrix<Number>& _dist, Geometric::Matrix<unsigned int>& _pre_node)
		{
			if(m_data->isValid() == true
				&& isValidNode(_start) == false)
			{
				// invalid node index
				return false;
			}

			// create temporary data
			unsigned int node_count = m_data->countNodes();
			bool* include = new bool[node_count];
			Number* dist = new Number[node_count];
			unsigned int* pre_node = new unsigned int[node_count];

			// initialize temporary data
			for(unsigned int i = 0; i < node_count; i++)
			{
				dist[i] = m_data->getEdgeValue(_start, i);
				include[i] = false;
				pre_node[i] = (isValidEdgeValue(dist[i]) == true) ? _start : _GraphStructure::getNPos();
			}

			// mark start node
			dist[_start] = _GraphStructure::getNumberZero();
			include[_start] = true;
			pre_node[_start] = _start;

			// select remain node
			for(unsigned int i = 0; i < node_count; i++)
			{
				Number min_num = _GraphStructure::getNumberEndless();
				unsigned int select_node = i;
				
				// find the node: min length
				for(unsigned int k = 0; k < node_count; k++)
				{
					if(include[k] == false && isValidEdgeValue(dist[k]) == true
						&& dist[k] < min_num)
					{
						select_node = k;
						min_num = dist[k];
					}
				}

				// can not find valid node
				if(isValidNode(select_node) == false)
				{
					break;
				}

				// mark the find node
				include[select_node] = true;

				// update the length array: start to any other node
				for(unsigned int j = 0; j < node_count; j++)
				{
					Number cur = m_data->getEdgeValue(select_node, j);
					if(isValidEdgeValue(cur) == true
						&& cur + dist[select_node] < dist[j])
					{
						dist[j] = cur + dist[select_node];
						pre_node[j] = select_node;
					}
				}
			}

			// assign the return value
			_dist.set(dist, 1, node_count);
			_pre_node.set(pre_node, 1, node_count);

			// free temporary data buffer
			delete[] include;
			delete[] dist;
			delete[] pre_node;

			// return true
			return true;
		}

		inline void doFloyd(Geometric::Matrix<Number>& _dist, Geometric::Matrix<unsigned int>& _path)
		{
			unsigned int node_count = m_data->countNodes();
			const Number& invalid = _GraphStructure::getNumberEndless();
			unsigned int npos = _GraphStructure::getNPos();
			
			_dist.alloc(node_count, node_count);
			_path.alloc(node_count, node_count);

			// initialize temporary data
			for(unsigned int i = 0; i < node_count; i++)
			{
				for(unsigned int j = 0; j < node_count; j++)
				{
					_dist.set(i, j, invalid);
					_path.set(i, j, npos);
				}
			}
			
			// iteration process
			for(unsigned int k = 0; k < node_count; k++)
			{
				for(unsigned int i = 0; i < node_count; i++)
				{
					for(unsigned int j = 0; j < node_count; j++)
					{
						Number number = _dist.at(i, k) + _dist.at(k, j);
						if(_dist.at(i, j) < number)
						{
							_dist.set(i, j) = number;
							_path.set(i, j) = k;
						}
					}
				}
			}
		}

	//public:
	//	inline bool getShortestPath(unsigned int _start, unsigned int _end, 
	//		Number& _length, std::vector<unsigned int>& _path)
	//	{
	//		// initialize return variable
	//		_length = _GraphStructure::getNumberEndless();
	//		_path.clear();

	//		// do Dijkstra-algorithm
	//		if(m_data->isValid() == true && isValidNode(_start) == true
	//			&& isValidNode(_end) == true)
	//		{
	//			Matrix<Number> dist;
	//			Matrix<unsigned int> path;
	//			if(doDijkstra(_start, dist, path) == true)
	//			{
	//				unsigned int vex = _end;
	//				unsigned int npos = _GraphStructure::getNPos();

	//				_length = dist.at(0, _end);

	//				// if start and end is connected
	//				if(_length != _GraphStructure::getNumberEndless())
	//				{
	//					while(vex != _start && vex != npos)
	//					{
	//						_path.push_back(vex);
	//						vex = path.at(0, vex);
	//					}
	//					// push start point into vector
	//					_path.push_back(vex);
	//				}

	//				// finish
	//				return true;
	//			}
	//		}

	//		// invalid start node or end node
	//		return false;			
	//	}
	};
}

#endif